package 递归回溯;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-05-20
 **/

public class No126单词接龙II {

    /**
     * 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
     * 每对相邻的单词之间仅有单个字母不同。
     * 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
     * sk == endWord
     * 给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。
     *
     * 示例 1：
     * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
     * 输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
     * 解释：存在 2 种最短的转换序列：
     * "hit" -> "hot" -> "dot" -> "dog" -> "cog"
     * "hit" -> "hot" -> "lot" -> "log" -> "cog"
     * 示例 2：
     * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
     * 输出：[]
     * 解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。
     *
     * 提示：
     * 1 <= beginWord.length <= 7
     * endWord.length == beginWord.length
     * 1 <= wordList.length <= 5000
     * wordList[i].length == beginWord.length
     * beginWord、endWord 和 wordList[i] 由小写英文字母组成
     * beginWord != endWord
     * wordList 中的所有单词 互不相同
     */

    /**
     * 不错的讲义:
     * https://leetcode-cn.com/problems/word-ladder-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-3-3/
     */

    private List<List<String>> result =new ArrayList<>();
    private Map<String,Set<String>> strChildrenSetMap;
    private Map<String,Integer> minDeepMap;
    private String targetStr;

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {

        Set<String> set=new HashSet<>(wordList);

        Map<String,Set<String>> map=new HashMap<>();

        //每个str的孩子set
        for (String str : wordList) {
            map.put(str,findReplaceOneStr(str,set));
        }
        //beginWord可能不在wordList中,所以要来一次
        map.put(beginWord,findReplaceOneStr(beginWord,set));

        this.strChildrenSetMap=map;

        //初始化str的minDeep
        this.minDeepMap=new HashMap<>();

        this.targetStr =endWord;

        //然后开始dfs
        ArrayList<String> path = new ArrayList<>();
        path.add(beginWord);
        HashSet<String> pathSet=new HashSet<>();
        pathSet.add(beginWord);
        this.dfs(beginWord,path,pathSet,0);

        return result;
    }

    private void dfs(String str,List<String> path,Set<String> pathSet,int deep) {

        if(str.equals(targetStr)){
            if(result.size()!=0){
                if(result.get(0).size()>path.size()){
                    result.clear();
                    result.add(new ArrayList<>(path));
                }else if(result.get(0).size()==path.size()){
                    result.add(new ArrayList<>(path));
                }
            }else{
                result.add(new ArrayList<>(path));
            }
            return;
        }

        Set<String> set = strChildrenSetMap.get(str);

        if(set==null){
            return;
        }

        for (String cStr : set) {

            if(pathSet.contains(cStr)){
                continue;
            }
            Integer cDeep = minDeepMap.get(cStr);
            //同级别的可以通过
            if(cDeep!=null&&cDeep<deep){
                continue;
            }

            pathSet.add(cStr);
            path.add(cStr);
            minDeepMap.put(cStr,deep);
            dfs(cStr,path,pathSet,deep+1);
            pathSet.remove(cStr);
            path.remove(path.size()-1);

        }

    }

    /**
     * 找到当前str1 可替换一个字母 得到的List<str2>集合(str2必须在List中)
     */
    public Set<String> findReplaceOneStr(String str,Set<String> wordList) {
        Set<String> childSet=new HashSet<>();
        for (int i = 0; i < str.length(); i++) {
            char[] arr = str.toCharArray();
            for (char j = 'a'; j <= 'z'; j++) {
                //替换当前位为 'a'~'z',然后查看是否在wordList中
                arr[i]=j;
                String str2 = String.valueOf(arr);
                if(str2.equals(str)){
                    continue;
                }
                if(wordList.contains(str2)){
                    childSet.add(str2);
                }
            }

        }
        return childSet;
    }

    public static void main(String[] args) {
        No126单词接龙II n=new No126单词接龙II();
        List<List<String>> result = n.findLadders("hit", "cog", Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
        System.out.println(JSON.toJSONString(result));
    }

}
